package fun.ticsmyc.dataStructure;

/**
 * 字典树
 * 解决：字符串存储和查询
 * @author Ticsmyc
 * @date 2021-03-30 11:12
 */
public class Trie {
    public Node root;
    public Trie(){
        root =  new Node();
    }

    /**
     * 插入一个字符串
     * @param s
     */
    public void insert(String s){
        Node cur = this.root;
        char[] str = s.toCharArray();
        for(int i=0;i<str.length;++i){
            int idx = str[i]-'a';
            if(cur.branches[idx] == null){
                cur.branches[idx] = new Node();
            }
            cur = cur.branches[idx];
            cur.val +=1;
        }
        cur.endCount+=1;
    }

    /**
     * 统计某个字符串出现次数
     * @param s
     * @return
     */
    public int count(String s){
        Node cur =this.root;
        char[] str= s.toCharArray();
        for(int i=0;i<str.length;++i){
            int idx=  str[i]-'a';
            if(cur.branches[idx]==null){
                return 0;
            }
            cur=cur.branches[idx];
        }
        return cur.endCount;
    }

    /**
     * 统计某个前缀出现次数
     * @param prefix
     * @return
     */
    public int startsWith(String prefix){
        Node cur =this.root;
        char[] pre = prefix.toCharArray();
        for(int i=0;i<pre.length;++i){
            int idx = pre[i]-'a';
            if(cur.branches[idx] == null){
                return 0;
            }
            cur = cur.branches[idx];
        }
        return cur.val;
    }


    private class Node{
        public int val =0;//经过这个node的路径
        public int endCount=0; //以这个node结尾的路径
        public Node[] branches = new Node[26]; //下一个分支
    }
}
